/**
 * 153. 寻找旋转排序数组中的最小值【中等】（与 154，剑指 Offer 11 同）
 * https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/
 */
public class Solutions_153 {
    public static void main(String[] args) {
//        int[] nums = {3, 4, 5, 1, 2};  // output: 1
//        int[] nums = {4, 5, 6, 7, 0, 1, 2};  // output: 0
//        int[] nums = {1, 3, 5};  // output: 1
//        int[] nums = {2, 2, 2, 0, 1};  // output: 0
        int[] nums = {3, 1};  // output: 1

        int result = findMin(nums);
        System.out.println(result);
    }

    /**
     * 二分查找法
     */
    public static int findMin(int[] nums) {
        if (nums == null || nums.length < 1) {
            // 没有元素
            return -1;
        }
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[right]) {
                // nums[mid] 后的元素都大于 nums[mid]，那么最小值一定存在于 [left, mid] 中
                right = mid;
            } else {
                // nums[mid] 后的元素一定存在着翻转后的元素，那么最小值
                // 一定存在于 [mid + 1, right] 中
                left = mid + 1;
            }
        }
        return nums[left];
    }

    /**
     * 线性查找法，效率较差
     * [0, len - 1] 中的每个元素，与其后一个元素比较，大于后一个元素时，后一个元素一定是最小元素
     */
    public static int findMin2(int[] nums) {
        if (nums == null || nums.length < 1) {
            return -1;
        }
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                // 找到翻转后的起点，即最小的元素
                return nums[i + 1];
            }
        }
        return nums[0];
    }
}
